package com.gxc.string;

/**
 *  一个完整的括号字符串定义规则如下
 *   1)空字符串是完整的。
 *   2)如果s是完整的字符串，那么(s)也是完整的。
 *   3)如果s和t是完整的字符串，将它们连接起来形成的st也是完整的。
 *   例如，"(())”，“"和”(())()“是完整的括号字符串，”())(””()(”和“)"是不完整的括号字符串。
 *   有一个括号字符串s,现在需要在其中任意位置尽量少地添加括号.将其转化为一个完整的括号字符串。
 *   请问至少需要添加多少个括号。
 *
 *   方案：
 *      字符遍历
 *      设置一个count，遇到字符 (，count++,
 *      遇到字符 ), count--
 *      最后count>0,则最后需要添加 i 个 (
 *      当count<0, 则需要立即添加 一个 )
 *      count = 0，是完整的括号字符串
 */
public class AddParentheses {

    public static void main(String[] args) {

    }

    /**
     *
     * @param str
     */
    public int addParentheses(String str) {
        //剩余 ( 的数量
        int count = 0;
        //总共需要补充的 ( ) 的数量
        int sum = 0;
        for (int i = 0;i<str.length();i++) {
            if (str.charAt(i) == '(') {
                count++;
            } else if (str.charAt(i) == ')') {
                //当发现 ) 数量大于 ( 时，需要立即补充一个 (
                if (count == 0) {
                    sum++;
                } else {
                    count--;
                }
            }
        }
        return sum+count;
    }

}
